package basic.courseLearn05.problem;

import org.junit.Test;

import java.util.HashSet;

//链表相交问题
public class ListIntersection {

    //单链表的节点
    private class Node<T> {
        private T data;
        private Node<T> next;

        public Node() {
        }

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
        public Node(T data) {
            this.data = data;
        }
    }

    @Test
    //测试有环无环
    public void test() {
        //定义一个带有环的链表
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(2);
        Node<Integer> node3 = new Node<>(3);
        Node<Integer> node4 = new Node<>(4);
        Node<Integer> node5 = new Node<>(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;
//        node5.next = null;
        Node<Integer> head = node1;
        System.out.println("链表是否有环：" + ((hasCycle_solution1(node1)==null)?null:hasCycle_solution1(node1).data));
        System.out.println("链表是否有环：" + ((hasCycle_solution2(node1)==null)?null:hasCycle_solution2(node1).data));

    }
    @Test
    //测试链表相交1-1，无环vs无环，相交
    public void test_1_1() {
        //headA
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(3);
        Node<Integer> node3 = new Node<>(5);
        Node<Integer> node4 = new Node<>(7);
        Node<Integer> node5 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;
        Node<Integer> headA = node1;
        //headB
        Node<Integer> node6 = new Node<>(4);
        node6.next = node3;
        Node<Integer> headB = node6;
        System.out.println("链表是否相交：" + ((getIntersectionNode(headA,headB)==null)?null:getIntersectionNode(headA,headB).data));

    }
    @Test
    //测试链表相交1-2，无环vs无环，不相交
    public void test_1_2() {
        //headA
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(3);
        Node<Integer> node3 = new Node<>(5);
        Node<Integer> node4 = new Node<>(7);
        Node<Integer> node5 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;
        Node<Integer> headA = node1;
        //headB
        Node<Integer> node6 = new Node<>(2);
        Node<Integer> node7 = new Node<>(4);
        Node<Integer> node8 = new Node<>(6);
        Node<Integer> node9 = new Node<>(8);
        Node<Integer> node10 = new Node<>(10);
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = null;
        Node<Integer> headB = node6;
        System.out.println("链表是否相交：" + ((getIntersectionNode(headA,headB)==null)?null:getIntersectionNode(headA,headB).data));

    }
    @Test
    //测试链表相交2，无环vs有环，不相交
    public void test_2() {
        //headA
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(3);
        Node<Integer> node3 = new Node<>(5);
        Node<Integer> node4 = new Node<>(7);
        Node<Integer> node5 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;
        Node<Integer> headA = node1;
        //headB
        Node<Integer> node6 = new Node<>(2);
        Node<Integer> node7 = new Node<>(4);
        Node<Integer> node8 = new Node<>(6);
        Node<Integer> node9 = new Node<>(8);
        Node<Integer> node10 = new Node<>(10);
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = node9;
        Node<Integer> headB = node6;
        System.out.println("链表是否相交：" + ((getIntersectionNode(headA,headB)==null)?null:getIntersectionNode(headA,headB).data));

    }
    @Test
    //测试链表相交3-1，相交，环点相同
    public void test_3_1() {
        //headA
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(3);
        Node<Integer> node3 = new Node<>(5);
        Node<Integer> node4 = new Node<>(7);
        Node<Integer> node5 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;
        Node<Integer> headA = node1;
        //headB
        Node<Integer> node6 = new Node<>(2);
        node6.next = node3;
        Node<Integer> headB = node6;
        System.out.println("链表是否相交：" + ((getIntersectionNode(headA,headB)==null)?null:getIntersectionNode(headA,headB).data));

    }
    @Test
    //测试链表相交3-2，相交，环点不同
    public void test_3_2() {
        //headA
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(3);
        Node<Integer> node3 = new Node<>(5);
        Node<Integer> node4 = new Node<>(7);
        Node<Integer> node5 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;
        Node<Integer> headA = node1;
        //headB
        Node<Integer> node6 = new Node<>(2);
        node6.next = node4;
        Node<Integer> headB = node6;
        System.out.println("链表是否相交：" + ((getIntersectionNode(headA,headB)==null)?null:getIntersectionNode(headA,headB).data));

    }
    @Test
    //测试链表相交3-3，不相交
    public void test_3_3() {
        //headA
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(3);
        Node<Integer> node3 = new Node<>(5);
        Node<Integer> node4 = new Node<>(7);
        Node<Integer> node5 = new Node<>(9);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;
        Node<Integer> headA = node1;
        //headB
        Node<Integer> node6 = new Node<>(2);
        Node<Integer> node7 = new Node<>(4);
        Node<Integer> node8 = new Node<>(6);
        Node<Integer> node9 = new Node<>(8);
        Node<Integer> node10 = new Node<>(10);
        node6.next = node7;
        node7.next = node8;
        node8.next = node9;
        node9.next = node10;
        node10.next = node8;
        Node<Integer> headB = node6;
        System.out.println("链表是否相交：" + ((getIntersectionNode(headA,headB)==null)?null:getIntersectionNode(headA,headB).data));

    }




    //问题拆分1：判断单链表是否有环
    /**
     * 判断单链表是否有环--方法1：利用HashSet
     * @param head 链表头节点
     * @return  返回第一个环的入口节点，如果没有环，返回null
     */
    public Node<Integer> hasCycle_solution1(Node<Integer> head) {
        Node<Integer> temp = head;
        HashSet<Node<Integer>> set = new HashSet<>();
        while (temp!= null) {
            if (set.contains(temp)) {       //包含环，返回第一个环的入口节点
                return temp;
            } else {
                set.add(temp);
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * 判断单链表是否有环--方法1：利用快慢指针
     * @param head 链表头节点
     * @return  返回第一个环的入口节点，如果没有环，返回null
     */
    public Node<Integer> hasCycle_solution2(Node<Integer> head) {
        //1.定义变量
        Node<Integer> slow = head;
        Node<Integer> fast = head;
        if (fast == null || fast.next == null || fast.next.next == null){
            return null;
        }
        //2. 开始移动指针
        fast = fast.next.next;
        slow = slow.next;
        //3. 相遇情况
        while(true){
            if (fast.next == null || fast.next.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                break;
            }
        }
        //4. 找到环的入口节点
        fast=head;
        while (true){
            fast = fast.next;
            slow = slow.next;
            if (fast == slow){
                return fast;
            }
        }
    }

    //链表相交问题
    /**
     * 链表相交问题--分析各种情况
     * @param headA 链表A的头节点
     * @param headB 链表B的头节点
     * @return  返回相交节点的头节点，如果没有相交，返回null
     */
    public Node<Integer> getIntersectionNode(Node<Integer> headA, Node<Integer> headB) {
        //1.无环vs无环
        if (hasCycle_solution2(headA)==null && hasCycle_solution2(headB)==null){
            //1.1 相交
            int diffValue = calLinkListLength(headA) - calLinkListLength(headB);
            Node<Integer> tempA = headA;
            Node<Integer> tempB = headB;
            if (diffValue>0){
                while (diffValue>0){
                    tempA=tempA.next;
                    diffValue--;
                }
            }else{
                while (diffValue<0){
                    tempB=tempB.next;
                    diffValue++;
                }
            }
            while(true){
                if (tempA==tempB){
                    if (tempA==null){       //不相交
                        break;
                    }else {             //相交
                        return tempA;
                    }
                }
                tempA=tempA.next;
                tempB=tempB.next;
            }


        }
        //2.无环vs有环，不可能相交
        if ((hasCycle_solution2(headA)==null && hasCycle_solution2(headB)!=null) || (hasCycle_solution2(headA)!=null && hasCycle_solution2(headB)==null)){
            return null;
        }
        //3. 有环vs有环
        if (hasCycle_solution2(headA)!=null && hasCycle_solution2(headB)!=null){
            //3.1 相交情况
            if (hasCycle_solution2(headA) == hasCycle_solution2(headB)){        //环切点相同
                return hasCycle_solution2(headA);
            }else{              //环切点不同
                Node<Integer> tempA = hasCycle_solution2(headA);    //A等待
                Node<Integer> locationB = hasCycle_solution2(headB);    //B前进
                Node<Integer> tempB=locationB.next;
                while(true){
                    if (tempA==tempB){      //找到了相交点
                        return locationB;
                    }
                    if (tempB == locationB){    //绕了一圈还没找到
                        return null;
                    }
                    tempB=tempB.next;
                }
            }
        }

        return null;
    }

    /**
     * 计算单链表的长度
     * @param head 链表头节点
     * @return  返回链表长度
     */
    public Integer calLinkListLength(Node<Integer> head){
        int result=0;
        while (head!=null){
            result++;
            head=head.next;
        }
        return result;
    }








}
